package com.sicheng.lc.周赛.分类.队列;

import leetcode.editor.cn.tree.TreeNode;

import java.util.ArrayDeque;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/30 20:31
 */
public class 反转二叉树的奇数层 {
    static ArrayDeque<TreeNode> q = new ArrayDeque<>(1 << 14);
    static ArrayDeque<Integer> stack1 = new ArrayDeque<>();
    static ArrayDeque<Integer> stack2 = new ArrayDeque<>();

    //https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/
    public TreeNode reverseOddLevels(TreeNode root) {
        int step = 0;
        q.offer(root);

        while (!q.isEmpty()) {
            step++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                assert node != null;
                if (!stack1.isEmpty()) {
                    node.val = stack1.pop();
                }
                if (node.left != null) {
                    q.offer(node.left);
                    if ((step & 1) == 1)
                        stack2.push(node.left.val);
                }
                if (node.right != null) {
                    q.offer(node.right);
                    if ((step & 1) == 1)
                        stack2.push(node.right.val);
                }
            }
            ArrayDeque<Integer> t = stack1;
            stack1 = stack2;
            stack2 = t;
        }
        return root;
    }
}
